package leetcode;

public class PaintHouse {

	
	public static void main(String[] args) {
		PaintHouse object = new PaintHouse();
		int[][] house = {{1, 2, 3}, {1, 4, 6}};
		System.out.println(object.minCostII_2(house));
	}
	
	//一共有k种颜色，找到相邻房屋颜色都不相同的最小费用
	//O(n * k * k), 超时了
	public int minCostII(int[][] costs) {
        // Write your code here
        if (costs == null || costs.length <= 0){
            return 0;
        }
        int colors = costs[0].length;
        int[][] dp = new int[costs.length][colors];
        //
        for(int i = 0; i < colors; i++){
            dp[0][i] = costs[0][i];
        }
        
        for (int i = 1; i < costs.length; i++){
            for (int j = 0; j < colors; j++){
                int min = Integer.MAX_VALUE;
                for (int k = 0; k < colors; k++){
                    if (k == j){
                        continue;
                    }
                    int cur = dp[i - 1][k];
                    min = Math.min(cur, min);
                }
                dp[i][j] = min + costs[i][j];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < colors; j++){
            res = Math.min(res, dp[costs.length - 1][j]);
        }
        return res;
    }
	
	//O(n * k)
	public int minCostII_2(int[][] costs) {
        // Write your code here
        if (costs == null || costs.length <= 0){
            return 0;
        }
        int colors = costs[0].length;
        int[][] dp = new int[costs.length][colors];
        //
        for(int i = 0; i < colors; i++){
            dp[0][i] = costs[0][i];
        }
        
        //本来是需要两个数组的，一个记录从左往右0...i的最小值，一个记录从右往左的colors.length - 1...i的最小值
        //但是因为我们是从左往右遍历的，所以可以省掉一个数组的空间
        int[] min = new int[colors + 1];
        for (int i = 1; i < costs.length; i++){
        	min[colors] = Integer.MAX_VALUE;
        	min[colors - 1] = dp[i - 1][colors - 1];
        	for(int j = colors - 2; j >= 0; j--){
        		min[j] = Math.min(min[j + 1], dp[i - 1][j]);
        	}
        	int leftMin = Integer.MAX_VALUE;
        	for(int j = 0; j < colors; j++){
        		//还需要排除同颜色的
        		int minDiff = leftMin < min[j + 1] ? leftMin : min[j + 1];
        		dp[i][j]= minDiff + costs[i][j];
        		leftMin = Math.min(leftMin, dp[i - 1][j]);
        	}
                
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < colors; j++){
            res = Math.min(res, dp[costs.length - 1][j]);
        }
        return res;
    }
}
